/*
解题思路：前序非递归遍历需要借助栈
  1. 如果树为空，直接返回
  2. 如果树非空：从根节点位置开始遍历，因为前序遍历规则：根节点、左子树、右子树
      a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈，并访问。
      b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点，其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍历，继续a
具体实现：参考代码，学生自己动手画图理解
*/

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Solution4 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        while(null != cur || !s.empty())
        {
            // 每次循环表示要开始访问一颗树了，先将一颗树的左路节点都入栈并访问节点
            // 剩余左路节点的右子树还没访问
            while(null != cur)
            {
                ret.add(cur.val);
                s.push(cur);
                cur = cur.left;
            }


            // 取栈中的节点依次访问左路节点的右子树
            cur = s.pop();
            cur = cur.right;
        }
        return ret;
    }
}